#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    long long countQuadruplets(vector<int>& nums) {
        long long n = nums.size(), ret = 0;
        vector<vector<int>> great(n, vector<int>(n + 1));
        for (int k = n - 2; k >= 2; k--) {
            great[k] = great[k + 1];
            for (int x = 1; x < nums[k + 1]; x++) great[k][x]++;
        }
        vector<int> less(n + 1);
        for (int j = 1; j <= n - 3; j++) {
            for (int x = nums[j - 1] + 1; x <= n; x++) less[x]++;
            for (int k = j + 1; k < n - 1; k++) if (nums[j] > nums[k]) ret += less[nums[k]] * great[k][nums[j]];
        }
        return ret;
    }
};

class Solution {
public:
    long long countQuadruplets(vector<int>& nums) {
        long long n = nums.size(), cnt4 = 0;
        vector<int> cnt3(n);
        for (int l = 2; l < n; l++) {
            int cnt2 = 0;
            for (int j = 0; j < l; j++) {
                if (nums[j] < nums[l]) cnt4 += cnt3[j], cnt2++;
                else cnt3[j] += cnt2;
            }
        }
        return cnt4;
    }
};